Problem statement: zenit15kki

Interesantný strom

Počet bodov: 35, časový limit: 500ms

Počas prechádzky po záhrade v šatníku ste narazili na čudesný-prečudesný strom. Rástlo na ňom ovocie všelijakých druhov, zväčša takých, aké ste ešte nevideli. Dokonca na každej vetvičke (vačšinou) iné. Chceli by ste ochutnať čo najviac druhov, ale nemáte na to celý deň. Preto by sa vám hodilo v každom mieste, kde sa oddeľujú nejaké halúzky, vedieť, koľko rôznych druhov ovocia viete dosiahnuť, keď z tohoto vetviaceho miesta pôjdete iba hore, k ovociu.

Úloha

Tí z vás, ktorí sa už stretli s pojmom grafu, určite bez problémov zistia, čo znamenajú pojmy v nasledujúcom texte. Ostatní sa môžu pozrieť ďalej k príkladu, kde sa pokúsime pojmy, prípadne zadanie dostatočne dobre vysvetliť.

Dostanete popis zakoreneného stromu. V každom listovom vrchole rastie jeden druh ovocia, jeho druh dostaneme ako číslo. Vnútorným vrcholom označíme taký vrchol, ktorý má aspoň jedného syna.

Pre každý vnútorný vrchol stromu zistite, koľko rôznych druhov ovocia sa nachádza v jeho podstrome.

Popis stromu

Každý vnútorný vrchol s \(n\) synmi popíšeme ako \(( A_1 A_2 A_3 \cdots A_n)\), kde \(A_1, A_2, \cdots, A_n\) sú popisy jeho podstromov. Listový vrchol popíšeme ako \((x)\), kde \(x\) je číslo ovocia rastúceho v tomto vrchole.

Príklad stromu a jeho popisu:

\((_a(47)(_b(_c(2)(12))_c(_d(5))_d)_b)_a\)

Zakorenený strom \(((47)(((2)(12))((5))))\)

Za každú zátvorku sme si napísali pre názornosť číslo vrcholu, ktorého sa týka. Vo vstupe takéto označenie nebude.

Pojmy

Zakoreneným stromom nazveme útvar, ktorý máte na obrázku. Obsahuje nejaké vrcholy (označené krúžkami), ktoré sú medzi sebou poprepájané hranami (čiarami v obrázku). V našom strome sú všetky vrcholy spojené, aj keď niektoré len nepriamo (nemáme vrcholy \(A\) a \(B\) také, že nevieme nájsť cestu od \(A\) po \(B\) po nejakých hranách).

V každom zakorenenom strome platí, že si vieme vrcholy rozdeliť na úrovne tak, že z každej dvojice vrcholov bude jeden vyššie ako druhý a navyše máme presne povedané, ktorý vrchol je ten najvyšší. Uvedomte si, že toto nám určuje pre každú dvojicu spojených vrcholov, ktorý z nich bude vyššie a ktorý bude visieť. Navyše, každý vrchol (okrem najvyššieho) bude spojený len s jedným vyšším vrcholom

Vnútorným vrcholom nazveme taký, z ktorého visí (za hranu) nejaký iný vrchol, listovým nazveme naopak taký, z ktorého už žiaden vrchol nevisí. V príklade sú vnútorné vrcholy označené písmenkami a listové číslami.

Podstromom vrchola \(A\) nazveme množinu všetkých vrcholov, ktoré (priamo alebo nepriamo) visia z \(A\).

Vstup a výstup

Dostanete jeden riadok s horeuvedeným popisom stromu. Každé číslo bude mať pred sebou aj za sebou práve jednu medzeru, iné medzery na vstupe nebudú (viď príklady vstupov). Tento riadok bude mať nanajvýš \(100\, 000\) znakov a samotný strom bude mať nanajvýš \(10\, 000\) vnútorných vrcholov. Všetky čísla ovocí budú v rozsahu \(1\) až \(10\, 000\).

Pre každý vnútorný vrchol vypíšte počet rôznych druhov ovocia, ktorý sa vyskytuje v jeho podstrome, do samostatného riadka. Výsledky pre vrcholy vypisujte v takom poradí, v akom sa končí ich popis na vstupe. V názornom príklade budú teda vrcholy v poradí \(C, D, B, A\).

Takto zadaný popis stromu je dosť zložitý. Preto ak budete vedieť korektne riešiť túto úlohu pre strom, v ktorom každý vnútorný vrchol má práve dvoch synov a z toho ľavý je vždy listový, získate aspoň \(20\) bodov.

Príklady

Input:

(( 2 )( 1 ))

Output:

2

Input:

((( 3 )( 2 ))( 4 )( 2 ))

Output:

2
3

Prvý ukončený vnútorný vrchol obsahuje ovocie 2 a 3, druhý je už celý strom a ten obsahuje ovocie 2, 3 a 4, pričom ovocie 2 obsahuje dvakrát.

Input:

(( 1 )(( 2 )(( 3 )(( 4 )( 1 )))))

Output:

2
3
4
4

Toto je príklad jednoduchšieho vstupu. Každý vnútorný vrchol má práve dvoch synov a ľavý je listový. Najnižší vnútorný vrchol má dvoch listových synov.